def mergesort(arr):
    n = len(arr)
    if n <= 1:
        return arr
    res1 = mergesort(arr[:n//2])
    res2 = mergesort(arr[n//2:])
    return _merge(res1, res2)


def _merge(arr1, arr2):
    '''
    arr1 and arr2 are sorted
    '''
    res = []
    i, j = 0, 0
    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            res.append(arr1[i])
            i += 1
        else:
            res.append(arr2[j])
            j += 1
    
    res += arr1[i:] if i < len(arr1) else arr2[j:]
    return res


if __name__ == "__main__":
    print(mergesort([9, 2, 8]))
    print(mergesort([3, 6, 0, 4]))
    print(mergesort([1, 8, 7, 3, 6, 0, 4]))
